// kruskal 前置知识：链式前向星、并查集
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 500 * 500 + 7;
int bin[maxn];
int n, m;
struct edge {  // 链式前向星
    int u, v, w;
} edges[maxn];
// 并查集
inline void unit() {
    for (int i = 0; i <= m; i++) bin[i] = i;
}
inline int Find(int x) {
    int px = x;
    while (px != bin[px]) px = bin[px];
    return px;
}
inline void merge(int x, int y) {
    int fx = Find(x);
    int fy = Find(y);
    if (fx != fy) bin[fx] = fy;
}
inline bool cmp(edge a, edge b) {  //定义排序规则
    return a.w < b.w;
}
inline void Kruskal() {
    long long int sumweight = 0;  //生成树的权值
    int num = 0;                  //已选用的边的数目
    int u, v;                     //选用边的两个顶点
    unit();                       //初始化 parent[]数组
    for (int i = 0; i < m; i++) {
        u = edges[i].u;
        v = edges[i].v;
        if (Find(u) != Find(v)) {  //判断其是否在同一个连通分量
            sumweight += edges[i].w;
            num++;
            merge(u, v);
        }
        if (num >= n - 1) break;
    }
    printf("%lld\n", sumweight);
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);  //读入顶点个数 n
        int x;
        m = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                scanf("%d", &x);
                if (x) {
                    edges[m].u = i + 1;
                    edges[m].v = j + 1;
                    edges[m++].w = x;
                }
            }
        }
        sort(edges, edges + m, cmp);  //排序
        Kruskal();
    }
    return 0;
}